书本一道习题推导

Lagrange 对偶问题: 最小体积覆盖球问题的公式推导 中文版P221->5.2 \[ minimize:\ f(X) = log\ detX^{-1} \\ subject\ to:\ a_i^TXa_i \leq 1 , i = 1,\cdots ,m \] 先证明一个引理 \[Lemma:\ a^TXb=diag(ba^TX)\cdot\vec{1}\] \[令s表示上式结果,W=ba^TX, 则右端表示W对角线和\] \[s=a^TXb=\sum_i\sum_ja_iX_{ij}b_j\] \[s=\sum_iW_{ii}=\sum_i(\sum_jb_ia_j)X_{ji}=\sum_i\sum_ja_iX_{ij}b_j\] 证毕 原问题的Lagrange式 \[L(x,\lambda) = f(X) + \sum_{i=1}^m\lambda_i(a_i^TXa_i -1)\] 原问题的Lagrange对偶 \[g(\lambda) = \inf_x{L(x,\lambda)}\] 取L关于X的偏导数为0 \[\frac{\partial{L(x,\lambda)}}{\partial{X}} = -X^{-1} +\sum_{i=1}^m\lambda_ia_ia_i^T=0\] 则 \[X^{-1}=\sum_{i=1}^m\lambda_ia_ia_i^T\] \[g(\lambda)=log\ det(\sum_{i=1}^m\lambda_ia_ia_i^T)+\sum_{i=1}^m\lambda_ia_i^TX^{-1}a_i-1^T\lambda\] \[=log\ det(\sum_{i=1}^m\lambda_ia_ia_i^T)+diag((\sum_{i=1}^ma_ia_i^T)X^{-1})\cdot\vec{1}=diag(XX^{-1})\cdot\vec{1}-1^T\lambda\] \[=log\ det(\sum_{i=1}^m\lambda_ia_ia_i^T)+diag(I_n)\cdot\vec{1}-1^T\lambda=log\ det(\sum_{i=1}^m\lambda_ia_ia_i^T)+m-1^T\lambda\] 因此原问题的对偶问题为 \[maximize:\ g(\lambda)=log\ det(\sum_{i=1}^m\lambda_ia_ia_i^T)+m-1^T\lambda \] \[subject\ to:\ \lambda_i\geq0 , i = 1,\cdots ,m\]